# -*- coding: utf-8 -*-

"""139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同"""

class Solution:
    """
    定义 f(i) 为 [0,i] 片段是否可有字典凭借出
    递归定义：
        f(i) = f(i-p1) OR f(i-p2) OR f(i-p3) OR ... OR f(i-pn)         # s[i-px : i] 位于字典中
    递归基础：
        f(p1) = true        # s[0 : px] 开头位于字典中
        f(p2) = true
        f(p3) = true
        ...
        f(p4) = true

    将递归运算按动态规划，修改为以状态迁移的递推。
    """
    def wordBreak(self, s: str, wordDict: list) -> bool:
        prefixes = set()

        for word in wordDict:
            if s.startswith(word):
                if word == s:
                    return True
                else:
                    prefixes.add(word)

        if not prefixes:
            return False
        
        while True:
            try:
                prefix = prefixes.pop()
            except KeyError:
                break

            for word in wordDict:
                longger = prefix+word
                if s.startswith(longger):
                    if s == longger:
                        return True
                    else:
                        prefixes.add(longger)

        return False

if __name__ == '__main__':
    print(Solution().wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]))
